1. Field of the Invention
The present invention relates to a variable length code decoder for decoding a variable length code such as a Huffman code or the like and which is suitable for use in transmitting image data and audio data in the form of compressed data.
2. Description of the Prior Art
When a large amount of data such as image data or the like is transmitted by using a communication network whose data transfer capability is limited or when image data of a long period of time is recorded on a storage medium of a small storage capacity and so on, bit-rate reduction technologies may be utilized for reducing the data amount.
With regard to the bit-rate reduction technology, many technologies have heretofore been developed and put into practical use, such as a DCT (discrete cosine transform) coding technique in which image data, for example, is cosine-transformed and then compressed by using a coefficient thereof and a variable length coding technique in which an overall code amount is reduced by varying a length of a corresponding code in accordance with a frequency at which data is produced.
As an example of a variable length coding, there is proposed a Huffman coding. The fundamental concept of Huffman coding is that an average code length (or total code amount) is reduced by assigning a code of a short code length to an event (data) appearing with high frequency and by assigning a code of a long code length to an event appearing with low frequency to thereby compress data.
The system in which Huffman codes corresponding to respective event(s) in actual practice are generated depends upon the probability that the respective events occur. How to generate the Huffman code on the basis of statistics data of events had been described in various books under the title of information theory and therefore need not be described herein. In order to understand the present invention more clearly, a simple Huffman code corresponding to the following five data ("0", "1", "2", "3", "4") will be described. In the above-mentioned five data, more frequently occurring data, such as data having relatively small values, is represented by Huffman codes having a fewer number of digits as compared to data which occurs less frequently. As a result, such data may have the following Huffman code:
______________________________________ Data Huffman code ______________________________________ "0" [ 1] "1" [ 01] "2" [ 001] "3" [ 0001] "4" [00001] ______________________________________
By way of example, a Huffman code string having a data sequence of "2", "3", "0", "1", "3", "0", "4" is expressed as: EQU [00100011010001100001]
This data is output sequentially from the left-hand side.
FIG. 1 of the accompanying drawings shows an example of a conventional Huffman decoder for decoding the Huffman code.
As shown in FIG. 1, a Huffman code string is supplied to an input terminal 1. The Huffman code string is input to the input terminal 1 in the form of one bit serial data or in the unit of bytes or words depending upon a system bus width and an input and output method.
The Huffman code string from the input terminal 1 is temporarily stored in an n-bit register 2 where n is a value larger than a maximum length m of the Huffman code. Of the n-bit stored in the n-bit register 2, the m-bit indicative of the maximum length of the Huffman code is supplied to a decoder circuit 4 by a barrel shifter 3.
The barrel shifter 3 can shift the input code string during a constant time regardless of the number of bits to be shifted and is capable of high speed processing as compared with a shift register that shifts one bit by one clock pulse.
The decoder circuit 4 is comprised of a read-only memory (ROM), a programmable logic array (PLA), a logic gate or the like, though not shown. When the input signal becomes coincident with the Huffman code, the decoder circuit 4 outputs a hit signal at a hit signal output terminal 4a and also outputs decoded data at a data output terminal 5. Further, the decoder circuit 4 outputs a code length signal indicative of a length of Huffman code at that time to a code length signal output terminal 4b.
The hit signal developed at the hit signal output terminal 4a is supplied to a Huffman code decoder controller 6. The controller 6 supplies the decoded data of Huffman code to the next stage in response to the hit signal. The code length signal developed at the code length signal output terminal 4b is supplied to a shift controller 7 and the barrel shifter 3 is operated under the control of the shift controller 7 to supply the next input signal to the decoder circuit 4. When the Huffman signal becomes coincident with the input signal again, the decoder circuit 4 is operated similarly as described above to thereby sequentially decode the Huffman code string of the register 2.
When the Huffman code string that is input to the register 2 from the input terminal 1 has been decoded or processed, a new Huffman code is read out from the input terminal 1. The shift controller 7 includes, though not shown, an adder for accumulating or adding code lengths output from the decoder circuit 4, so as to control the shift amount of the barrel shifter 3 in a manner as more fully described hereinafter. As is to be appreciated, the accumulated or added code length is dependent upon the bit number n. When the code string input to the decoder circuit 4 is not coincident with the Huffman code (does not hit the Huffman code), it is determined that the input Huffman code has an error. Then, the Huffman code decoder moves to the error correction processing.
Operation of the Huffman decoder will be described together with the aforementioned Huffman code string with reference to FIGS. 2A through 2D.
FIG. 2A shows the condition that the Huffman code string is input to the register 2 in the initial state. At that time, the shift amount of the barrel shifter 3 is [0] and as shown in FIG. 2A, 5 bits (maximum code length of the Huffman code) on the left end of the register 2 are input to the decoder circuit 4.
In the decoder circuit 4, since data corresponding to 2" hits (becomes coincident with) the Huffman code, data "2" is output to the data output terminal 5 and the variable length signal "3" is output to the variable length code signal output terminal 4b. Then, under the control of the controller 6, the output data "2" from the decoder circuit 4 is supplied to the next stage. Accordingly, the shift amount [3] is added within the shift controller 7.
FIG. 2B shows the next condition. As shown in FIG. 2B, the shift amount of the barrel shifter 3 is [3] and 5 bits from the fourth bit from the left of the register 2 are supplied to the decoder circuit 4. The decoder circuit 4 outputs data "3" to the data output terminal 5 and the code length signal [4] to the code length signal output terminal 4b. Then, the code length [4] is accumulated within the shift controller 7 and the shift amount becomes [7].
FIG. 2C shows the next condition. As shown in FIG. 2C, the shift amount of the barrel shifter 3 becomes [7] so that 5 bits from the 8th bit from the left of the register 2 are input to the decoder circuit 4. The aforesaid operation is continuously carried out sequentially.
A delay in a loop of the barrel shifter 3, the decoder circuit 4 and the shift controller 7 shown in FIG. 1 becomes the most important problem when the Huffman decoder is designed so as to operate at high speed. If the Huffman decoder is designed as a high speed Huffman decoder that can process one data value in one clock pulse or period, there is then a restriction such that a total sum of a delay in a large barrel shifter (about 32 bits), delays in large ROM and PLA and a logic gate and a delay occurred when the shift amounts are added within the shift controller 7 must fall within one clock period. This restriction becomes severe from a hardware design standpoint.
It is considered that the above-mentioned loop is operated by 2 clocks in order to avoid the limit provided when the Huffman decoder is operated at high speed in the critical bus. At that time, the operation efficiency of the Huffman code decoder is lowered to the half.
As a picture quality of an image to be processed becomes high and the Huffman code string supplied to the input terminal 1 becomes high in bit rate in future, it is increasingly requested that the Huffman code decoder is able to operate at high speed.